#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    void spiral(vector<vector<int>>& matrix)
    {
        int n = matrix.size();
        int face = 0, cur = 1;
        bool turn = false;
        int i = 0, j = 0;
        while (cur <= (n * n))
        {
            matrix[i][j] = cur;
            if (cur == n * n)
                break;
            turn = false;
            switch (face)
            {
            case 0:
                if (j + 1 >= n || matrix[i][j + 1] != 0)
                    turn = true;
                else
                    ++j;
                break;
            case 1:
                if (i + 1 >= n || matrix[i + 1][j] != 0)
                    turn = true;
                else
                    ++i;
                break;
            case 2:
                if (i - 1 < 0 || matrix[i - 1][j] != 0)
                    turn = true;
                else
                    --i;
                break;
            case 3:
                if (j - 1 < 0 || matrix[i][j - 1] != 0)
                    turn = true;
                else
                    --j;
                break;
            }
            if (turn)
                face = (face + 1) % 4;
            else
                ++cur;
        }
    }
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0));
        spiral(res);
        return res;
    }
};